1. Field of the Invention
The present invention relates to a multiplication circuit, and more in particular, to a multiplication circuit wherein the operational processing is pipelined.
2. Description of the Prior Art
FIG. 1 is a block diagram showing an arrangement of an 8 bits.times.8 bits secondary Booth's multiplier wherein applied is the arrangement of a multiplier as disclosed in Japanese Patent Application Laid-Open No. 58-31449 (1983).
In FIG. 1, the numeral 1 denotes a first adding circuit for calculating the intermediate sums of partial products, while a numeral 3 a first storing circuit for storing the output from the first adding circuit 1.
A numeral 2 denotes a second adding circuit. Here the product output is calculated from the outputs from the first adding circuit 1 stored in the first storing circuit 3, namely, the outputs of the intermediate sums, as inputs. The product output from the second adding circuit 2, that is, the multiplication result is stored in a second storing circuit 4.
Both the first adding circuit 1 and the second adding circuit 2 comprise plural number of adders. In the drawing, characters HA and FA denote a half adder and a full adder respectively.
The operations of such a conventional multiplication circuit are as follows.
In FIG. 1, four partial products P.sub.i8 P.sub.i7 . . . P.sub.i0 (where i equals to 0, 1, 2, 3) found in accordance with Booth's algorithm are added in the first adding circuit 1 to obtain S.sub.j, C.sub.j (j=0.about.14), the outputs of the intermediate sums of the partial products. Thus found outputs of the intermediate sums are temporarily stored in the first storing circuit 3. Then the signals for the intermediate sums S.sub.j are added, while the carry signals C.sub.j are sequentially transmitted to the adjacent higher place between the half adders and full adders constituting the second adding circuit 2, to obtain the product output Zk (k=0.about.15), which is stored in the second storing circuit 4. This product output Zk is the multiplication result.
Therefore, in such a construction, it is possible that the partial products outputs found in the first adding circuit 1 are temporarily stored in the first storing circuit 3 and the next operation is executed in the first adding circuit 1, while the operations for obtaining this product output are being carried out in the second adding circuit 2. That is, it is possible to increase the operational efficiency by the pipelined processing of the multiplication at two stages, first in the first adding circuit 1 and, second in the second adding circuit 2.
The generating operations of the partial products and the operations in the first adding circuit 1 are hereinafter called the former-stage operations, while the operations in the second adding circuit 2 the latter-stage operations.
Among the signal transmitting paths leading to the output signals S.sub.j, C.sub.j in the former-stage operations, the longest are those of S.sub.6 to S.sub.10 and C.sub.7 to C.sub.11. Three adders (HA, FA) are provided on each of these paths. The paths leading to other output signals are shorter than the paths just referred to. Consequently, generated are differences in delayed time caused by the existence of adders (HA, FA) provided on the signal paths.
On the other hand, the output signal Zk in the latter-stage operations is found, carrying sequentially from higher places to lower ones. Therefore, the greater k is, the more time it requires in determining the value. For this reason, as the number of the half adders and the full adders constituting the second adding circuit 2, that is, the number of places of the multiplication numbers increases, it takes more time in carrying out the latter-stage operations.
Thus in a multiplication circuit wherein Booth's algorithm is utilized, more time is required in carrying out the latter-stage operations than in carrying out the former-stage operations. Consequently, the cycle is forced to be dependent on the time required for carrying out the latter-stage operations when the operations are carried out in the two-staged pipeline wherein one stage is assigned to each of the former-stage operations and the latter-stage operations.
Thus arranged is a conventional multiplication circuit. Therefore, the degree of parallel of operations remains on a low level, and there is a room for further improvements in shortening the entire processing time. Furthermore, in the latter-stage operations, if the number multiplied is n bit.times.n bit, transmissions of the carry signals are caused 2n-1 times to require more time than in the former-stage operations. Consequently, the cycle for the pipelined processing is forced to be dependent on the time required for the latter-stage operations when the two-staged pipelined processing is carried out. As a result, there arises a problem that the entire efficiency in carrying out the processing is lowered.